原文題目
Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

題目摘要

1. 題目給予一個 m×n 的二維二進位矩陣，其中每個元素可以是 '1'（代表陸地）或 '0'（代表水域）
2. 題目所求：回傳矩陣中的島嶼數量。

Example 1:

Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1

Example 2:

Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3

解題思路一

1. 初始化計數器：

   使用一個變數（如 result）來計數島嶼的數量。

2. 遍歷整個格子：

   • 使用兩層迴圈遍歷二維陣列中的每一個格子。
   • 檢查每一個格子的值。如果格子的值是 '1'（表示陸地），則這是一個新的島嶼的起點。

3. 啟動 DFS 探索：

   • 當我們發現一個新的 '1' 時，表示找到一個新的島嶼，將 result +1。
   • 呼叫 DFS 函數來探索這個島嶼。DFS 函數將從當前的格子開始，遞迴探索所有相連的陸地（上下左右）。

4. DFS 探索過程：

   • 在 DFS 函數中，首先要進行邊界檢查，確保當前格子在二維陣列範圍內。
   • 確保當前格子是 '1'（尚未被標記為已訪問的陸地），否則返回。
   • 將當前格子標記為已訪問（可以改成 '0'），防止重複訪問。
   • 遞迴探索當前格子的上下左右四個相鄰格子。

5. 回傳結果：

   回傳 result 的值，即島嶼的總數。

程式碼一

class Solution {
    public int numIslands(char[][] grid) {
        int result=0; //用作計島嶼個數
        for(int i=0; i<grid.length; i++){
            for(int j=0; j<grid[0].length; j++){
                //如果是陸地，島嶼數+1，並探索島嶼大小
                if(grid[i][j]=='1'){
                    result++;
                    DFS(grid, i, j);
                }
            }
        }return result;
    }
    private void DFS(char[][] grid, int a, int b){
        //邊界檢查：確保不超出陣列範圍並且格子是'1'
        if (a < 0 || a >= grid.length || b < 0 || b >= grid[0].length || grid[a][b] == '0') {
            return;
        }
        //將當前格子標記為已訪問（改成'0'）
        grid[a][b]='0';
        //遞迴探索四個方向（上、下、左、右）
        DFS(grid, a-1, b);
        DFS(grid, a+1, b);
        DFS(grid, a, b-1);
        DFS(grid, a, b+1);
    }
}

解題思路二

1. 設定變數：
   • 設立一些邊數來記錄矩陣的行數和列數，及發現的島嶼數量。
2. 遍歷矩陣：
   • 遍歷矩陣中的每個格子，當遇到陸地時，說明發現了一個新的島嶼，將島嶼數量加一，並啟動 BFS 來探索這個島嶼。
3. 廣度優先搜尋（BFS）：
   • 定義一個 bfs 方法，利用佇列來實現 BFS。
   • 將當前發現的陸地加入佇列，並將該位置標記為已訪問。
   • 透過 BFS 逐步訪問當前格子的四個相鄰方向（上、下、左、右）。如果相鄰位置也是陸地，則將其加入佇列並繼續探索，直到所有與當前島嶼相連的陸地都被標記為止。
4. 回傳結果：
   • 在完成整個矩陣的遍歷後，回傳最終的島嶼數量。

程式碼二

class Solution {
    public int numIslands(char[][] grid) {      
        int numIslands = 0; //設立計算島嶼數量的變數
        int row = grid.length; //獲取矩陣列數
        int column = grid[0].length; //獲取矩陣行數
        
        //遍歷矩陣中每個元素
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < column; j++) {
                //當發現陸地時，說明找到一個新的島嶼，所以島嶼數量加一，接著開始開始BFS走訪並標記整個島嶼
                if (grid[i][j] == '1') {
                    numIslands++;
                    bfs(grid, i, j, row, column); 
                }
            }
        }
        return numIslands; //回傳最終的島嶼數量
    }
    
    //設立BFS走訪方法用來標記從當前的陸地位置開始的整個島嶼
    private void bfs(char[][] grid, int i, int j, int row, int column) {        
        //定義四個方向的移動量（上下左右），用來遍歷相鄰格子
        int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        
        Queue<int[]> queue = new LinkedList<>(); //設立佇列來完成BFS走訪
        queue.offer(new int[]{i, j}); //將當前位置放入佇列
        grid[i][j] = '0'; //將當前陸地標記為已訪問
        
        //如果佇列不為空時就重複執行
        while (!queue.isEmpty()) {
            int[] current = queue.poll(); //從佇列中取出當前節點
            int currentRow = current[0]; //獲取當前節點的列
            int currentColumn = current[1]; //獲取當前節點的行
            
            //遍歷相鄰的四個方向
            for (int[] direction : directions) {
                int newRow = currentRow + direction[0]; //獲取相鄰節點的列
                int newColumn = currentColumn + direction[1]; //獲取相鄰節點的行
                
                //判斷相鄰位置是否在矩陣範圍內且是否為未訪問的陸地
                if (newRow >= 0 && newRow < row && newColumn >= 0 && newColumn < column && grid[newRow][newColumn] == '1') {
                    queue.offer(new int[]{newRow, newColumn}); //如果符合條件，將該位置加入佇列以便後續探索
                    grid[newRow][newColumn] = '0'; //將這塊新的陸地標記為已訪問
                }
            }
        }
    }
}

結論
這題題目我和我的組員分別利用深度優先搜尋（DFS）和廣度優先搜尋（BFS）來解題。 DFS 透過遞迴遍歷，每當發現新的陸地會以該點為起點，不斷向四周擴展，直到整個島嶼的所有連接塊都被訪問完畢。這個方法比較簡單直觀，尤其適合遞迴解題，但在深度較大的情況下可能會導致遞迴過深的問題。 BFS 會使用佇列來處理，每當發現一個新的陸地，將該陸地放入佇列並逐步探索它的相鄰陸地，直到整個島嶼被完全標記。這個方法避免了遞迴深度的問題，更適合用來處理大規模圖形的遍歷。所以雖然 DFS 較為簡單、容易實現，但在遞迴深度較大時可能不如 BFS 穩定，而 BFS 方法雖然稍微複雜，但更加高效且具有更好的可控性。